package linex

import (
	"fmt"
	"strings"
)

// 前缀数-节点 模块
type node struct {
	pattern  string  // 待匹配的全路由 /a/b/c
	part     string  // 路由一部分 a
	children []*node // 子节点
	isWild   bool    // 是否为模糊匹配 part含有 : 或 * 时 为 true
}

func NewNode() *node {
	return &node{
		pattern: "",
		part: "",
		children: make([]*node, 0),
		isWild: false,
	}
}

// 第一个成功匹配的节点
func (n *node) matchChild(part string) *node {
	for _, child := range n.children {
		if child.part == part || child.isWild {
			return child
		}
	}
	return nil
}

// 所有成功匹配的节点
func (n *node) matchChildren(part string) []*node {
	nodes := make([]*node, 0)
	for _, child := range n.children {
		if child.part == part || child.isWild {
			nodes = append(nodes, child)
		}
	}
	return nodes
}

// 插入节点
func (n *node) insert(pattern string, parts []string, height int) {
	// 层数符合，赋值
	fmt.Println(n.pattern)
	if len(parts) == height {
		// 叶子节点的pattern字段 = 目标pattern
		n.pattern = pattern
		return
	}
	// 先取出当前层数对应的 part
	part := parts[height]
	child := n.matchChild(part)
	// 没找到part，新赋值一个 node
	if child == nil {
		child = &node{
			part:   part,
			isWild: part[0] == ':' || part[0] == '*',
		}
		n.children = append(n.children, child)
	}
	// 递归
	child.insert(pattern, parts, height+1)
}

func (n *node) search(parts []string, height int) *node {
	// part层数与路由层数相同
	if len(parts) == height || strings.HasPrefix(n.part, "*") {
		if n.pattern == "" {
			return nil
		}
		return n
	}
	// 得到当前层数的路由值
	part := parts[height]
	children := n.matchChildren(part)

	for _, child := range children {
		// 递归查找
		result := child.search(parts, height+1)
		// 找到节点 直接返回
		if result != nil {
			return result
		}
	}
	return nil
}